package discrete.math;

import java.util.ArrayList;

/**
 * Determine the number of paths based on the size of the paths and 2 points.
 * Determine the actual paths based on the size and the 2 points
 * 
 */
public class Paths {

	static int[][] newMatrix;
	ArrayList<String> paths;

	/**
	 * Receives a filled matrix, two vertices, and size of path to calculate.
	 * Returns the numbers of paths
	 * 
	 * @param matrix
	 *            a filled matrix
	 * @param sizePath
	 *            number of paths
	 * @param vertix1
	 *            the row to calculate path
	 * @param vertix2
	 *            the column to calculate path
	 * @return number of paths to the 2 vertices based on the size of path
	 */
	public Paths(MatrixMath matrix) {
		newMatrix = new int[matrix.getMrows() - 1][matrix.getMcolumns() - 1];
		newMatrix = trimMatrix(matrix);
		paths = new ArrayList<String>();
	}

	private int[][] trimMatrix(MatrixMath matrix) {
		for (int i = 0; i < matrix.getMrows() - 1; i++) {
			for (int j = 0; j < matrix.getMcolumns() - 1; j++) {
				newMatrix[i][j] = matrix.lmatrix[i + 1][j + 1];
			}
		}
		return newMatrix;
	}

	public ArrayList<String> createRecursivePaths(char start, char end,
			int pathLength, int numVertices) {
		String newStr = "";
		getRecursivePaths(start, end, pathLength, numVertices, newStr);
		return paths;
	}

	public void getRecursivePaths(char start, char end, int pathLength,
			int numVertices, String newStr) {
		StringBuilder bstring = new StringBuilder();
		bstring.append(newStr).append(start);
		int advance = 0;
		boolean bad = false;
		while (!bad) {
			if (bstring.length() == pathLength + 1) {
				if (bstring.charAt(bstring.length() - 1) == end) {
					// then add to array list (this is the base case}
					paths.add(bstring.toString());
				}
				return;
				// newStr.deleteCharAt(newStr.length()-1);
			}
			if (advance >= newMatrix.length)
				return;
			if (newMatrix[start - 'A'][advance] == 1) {
				newStr = bstring.toString();
				getRecursivePaths((char) (advance + 'A'), end, pathLength,
						numVertices, newStr);
			}
			advance++;
		}
	}

	/**
	 * Creates all the know paths based on the starting and end points that is
	 * given
	 * 
	 * @param matrix
	 *            the matrix to find the paths
	 * @param start
	 *            start character ex. 'A'
	 * @param end
	 *            end character ex. 'B'
	 * @param pathLength
	 *            length of the paths to find
	 * @param numVertices
	 *            the number of vertices in the matrix
	 * @return
	 */
	public ArrayList<String> createPaths(char start, char end, int pathLength,
			int numVertices) {
		StringBuffer buffer = new StringBuffer(""); // always needs one n
		// String[] c = new String[pathLength + 1];

		buffer.append(start);
		buffer.append(start);
		for (int i = 0; i < pathLength; i++) {
			buffer.append('A');
		}
		int offset = buffer.length() - 1;
		while (buffer.charAt(0) == start) {
			System.out.println(buffer.substring(1));
			buffer.setCharAt(offset, (char) (buffer.charAt(offset) + 1));
			// Check if character went out of range, and bump
			for (int i = offset; i >= 0; i--) {
				if (buffer.charAt(i) > 'A' + numVertices) {
					buffer.setCharAt(i, 'A');
					buffer.setCharAt(i - 1, (char) (buffer.charAt(i - 1) + 1));
				} else {
					break;
				}
			}
			String str = new String(buffer.substring(1));
			if (checkPath(str, start, end, numVertices)) {
				paths.add(str);
				// System.out.println(buffer.substring(1));
			}
		}

		return paths;
	}

	/**
	 * Checks to see if the paths are good
	 * 
	 * @param string
	 *            the string containing the path
	 * @param startPoint
	 *            starting point
	 * @param endPoint
	 *            ending point
	 * @param numVertices
	 *            number of vertices in the matrix
	 * @return true if the path is good
	 */
	private boolean checkPath(String string, char startPoint, char endPoint,
			int numVertices) {
		Boolean result = true;

		// check to see if start matches actual start
		if (string.charAt(0) != startPoint) {
			return false;
			// check to see if the end matches the actual end
		} else if (string.charAt(string.length() - 1) != endPoint) {
			return false;
		} else {
			// checks for any duplicate points and out of range
			for (int i = 0; i < string.length(); i++) {
				if (i >= 0 && i <= string.length() - 2) {
					if (string.charAt(i) == string.charAt(i + 1)
							|| string.charAt(i) >= numVertices + 65) {
						return false;
					}
				}
			}
			// this is to remove invalid paths based on the matrix
			int j, k;
			for (int i = 0; i < string.length(); i++) {
				if (i >= 0 && i <= string.length() - 2) {
					j = string.charAt(i) - 65;
					k = string.charAt(i + 1) - 65;
					if (j >= 0 && j <= newMatrix.length - 1) {
						if (k >= 0 && k <= newMatrix.length - 1) {
							if (newMatrix[j][k] == 0) {
								return false;
							}
						}

					}
				}

			}
		}
		return result;
	}

	/**
	 * Calculates the number of paths give the matrix, size and the two vertices
	 * 
	 * @param matrix
	 * @param sizePath
	 * @param vertix1
	 * @param vertix2
	 * @return the number of paths
	 */
	public static int numberPaths(int sizePath, int vertix1, int vertix2) {
		int[][] mulMatrix = new int[newMatrix.length][newMatrix.length];
		mulMatrix = newMatrix.clone();
		for (int i = 1; i < sizePath; i++) {
			mulMatrix = Paths.mmult(mulMatrix, newMatrix);
		}
		int result = 0;
		result = mulMatrix[vertix1][vertix2];
		return result;
	}

	/**
	 * Multiplies the matrix based on the path length
	 * 
	 * @param A
	 * @param pathLength
	 * @return a new matrix with the calculated paths
	 */
	static int[][] mmult(int[][] A, int[][] B) {
		int i, j, k; // loop counters

		int ax; // accumulator for matrix multiplication

		int[][] C = new int[A.length][A.length];
		for (i = 0; i < A.length; i++) {
			for (j = 0; j < A.length; j++) {
				ax = 0; // reset accumulator

				for (k = 0; k < A.length; k++) {
					ax = ax + (A[i][k] * B[k][j]);
				}
				C[i][j] = ax;
			}
		}
		return C;
	}
	/**
	 * Gets the number of vertices on the matrix
	 * 
	 * @param matrix
	 * @return the number of vertices
	 */
	// static int getNumberVertices(int[][] matrix) {
	// int result = 0;
	// result = matrix.length;
	// return result;
	// }
}
